import java.util.TreeMap;

public class AVLTree {
    static class TreeNode{
        public TreeNode left;//左孩子节点
        public TreeNode right;//有孩子节点
        public TreeNode parent;//父亲节点
        public int bf;//平衡因子
        public int val;

        public TreeNode(int val){
            this.val = val;
        }
    }

    public TreeNode root;//

    public boolean insert(int val){
        TreeNode node = new TreeNode(val);
        if(root == null){
            root = node;
            return true;
        }

        TreeNode cur = root;
        TreeNode parent = null;

        while(cur != null){
            if(cur.val == val){
                return false;
            }else if(cur.val > val){
                parent = cur;
                cur = cur.left;
            }else{
                parent = cur;
                cur = cur.right;
            }
        }

        //cur == null
        /*if(parent.left == cur){
            parent.left = node;
        }else {
            parent.right = node;
        }*/
        if(parent.val > val){
            parent.left = node;
        }else {
            parent.right = node;
        }
        node.parent = parent;
        cur = node;

        //平衡因子的修改
        while(parent != null){
            //判断cur在parent的左边还是右边，左边--，右边++
            if(parent.left == cur){
                //如果是左树，那么左树高度增加 平衡因子--
                parent.bf--;
            }else {
                //如果是右树，那么右树高度增加 平衡因子++
                parent.bf++;
            }

            //检查当前的平衡因子 是不是绝对值 1 0 -1
            if(parent.bf == 0){
                //说明已经平衡了
                break;
            }else if(parent.bf == 1 || parent.bf == -1){
                //继续向上修改平衡因子
                cur = parent;
                parent = cur.parent;
            }else{
                //parent.bf == 2 || parent.bf == -2
                if(parent.bf == 2){//右树高 -> 降低右树的高度
                    if(cur.bf == 1){
                        //左旋
                        rotateLeft(parent);
                    }else{
                        //cur.bf == -1
                        rotateRL(parent);
                    }
                }else {
                    //parent.bf == -2 左树高 -> 需要降低左树的高度
                    if(cur.bf == -1){
                        //右旋
                        rotateRight(parent);
                    }else {
                        //cur.bf == 1
                        rotateLR(parent);
                    }
                }
                //上述代码走完就平衡了
                break;
            }
        }
        return true;
    }

    /**
     * 右左双旋
     * @param parent
     */
    private void rotateRL(TreeNode parent) {
        TreeNode subR = parent.right;
        TreeNode subRL = subR.left;
        int bf = subRL.bf;

        rotateRight(subR);
        rotateLeft(parent);

        if(bf == 1){
            parent.bf = -1;
            subR.bf = 0;
            subRL.bf = 0;
        }else if(bf == -1){
            parent.bf = 0;
            subR.bf = 1;
            subRL.bf = 0;
        }
    }

    /**
     * 左右双旋
     * @param parent
     */
    private void rotateLR(TreeNode parent) {
        TreeNode subL = parent.left;
        TreeNode subLR = subL.right;
        int bf = subLR.bf;

        rotateLeft(subL);
        rotateRight(parent);

        if(bf == 1){
            parent.bf = 0;
            subL.bf = -1;
            subLR.bf = 0;
        }else if(bf == -1){
            parent.bf = 1;
            subL.bf = 0;
            subLR.bf = 0;
        }
    }

    /**
     * 右单旋
     * @param parent
     */
    private void rotateRight(TreeNode parent) {
        TreeNode subL = parent.left;
        TreeNode subLR = subL.right;

        parent.left = subLR;
        subL.right = parent;

        TreeNode pParent = parent.parent;
        parent.parent = subL;

        if (subLR != null){
            subLR.parent = parent;
        }

        //检查当前是否是根节点
        if(parent == root){
            root = subL;
            subL.parent = null;
        }else {
            //不是根节点，判断这颗子树是左子树还是右子树
            if (pParent.left == parent){
                pParent.left = subL;
            }else {
                pParent.right = subL;
            }
            subL.parent = pParent;
        }

        parent.bf = subL.bf = 0;
    }

    /**
     * 左单旋
     * @param parent
     */
    private void rotateLeft(TreeNode parent) {
        TreeNode subR = parent.right;
        TreeNode subRL = subR.left;

        parent.right = subRL;
        subR.left = parent;

        TreeNode pParent = parent.parent;
        parent.parent = subR;
        if (subRL != null){
            subRL.parent = parent;
        }

        if (parent == root){
            root = subR;
            subR.parent = null;
        }else {
            if(pParent.left == parent){
                pParent.left = subR;
            }else {
                pParent.right = subR;
            }
            subR.parent = pParent;
        }

        parent.bf = subR.bf = 0;
    }

    public boolean isBalance(TreeNode root){
        if(root == null){
            return true;
        }

        int leftH = height(root.left);
        int rightH = height(root.right);

        if(rightH - leftH != root.bf){
            System.out.println("平衡因子异常..");
            return false;
        }

        return Math.abs(rightH - leftH) <= 1
                && isBalance(root.left)
                && isBalance(root.right);
    }

    private int height(TreeNode root) {
        if(root == null){
            return 0;
        }

        int leftH = height(root.left);
        int rightH = height(root.right);

        return leftH > rightH ? leftH + 1 : rightH + 1;
    }

    public static void main(String[] args) {
        int[] arr = {4, 2, 6, 1, 3, 5, 15, 7, 16,14};
        AVLTree avlTree = new AVLTree();
        for(int i : arr){
            avlTree.insert(i);
        }
        TreeMap map = new TreeMap<>();
        map.remove()
        System.out.println(avlTree.isBalance(avlTree.root));
    }
}
